package cn.edu.ncepu;

import java.util.ArrayList;
import java.util.List;

public class Permutations {

    // 封装栈帧元素：剩余数组、当前数组、剩余选取数量
    private static class StackFrame<T> {
        List<T> remain;
        List<T> current;
        int n;

        public StackFrame(List<T> remain, List<T> current, int n) {
            this.remain = remain;
            this.current = current;
            this.n = n;
        }
    }

    /**
     * 非递归生成从数组中选取n个元素的排列
     * @param array 原始数组
     * @param n 选取元素个数
     * @return 排列结果列表
     * @param <T> 元素类型
     */
    public static <T> List<List<T>> permutations(List<T> array, int n) {
        List<List<T>> result = new ArrayList<>();
        // 初始化栈，存储StackFrame对象
        List<StackFrame<T>> stack = new ArrayList<>();
        stack.add(new StackFrame<>(new ArrayList<>(array), new ArrayList<>(), n));

        while (!stack.isEmpty()) {
            // 弹出栈顶元素（模拟Python的pop()）
            StackFrame<T> frame = stack.remove(stack.size() - 1);
            List<T> remain = frame.remain;
            List<T> current = frame.current;
            int remainNum = frame.n;

            // 选取数量为0时，将当前数组加入结果
            if (remainNum == 0) {
                result.add(current);
                continue;
            }

            // 遍历剩余数组，生成新的栈帧
            for (int i = 0; i < remain.size(); i++) {
                // 拷贝剩余数组并移除当前索引元素
                List<T> copyRemain = new ArrayList<>(remain);
                T x = copyRemain.remove(i);

                // 拷贝当前数组并添加选中元素
                List<T> newCurrent = new ArrayList<>(current);
                newCurrent.add(x);

                // 将新的栈帧压入栈
                stack.add(new StackFrame<>(copyRemain, newCurrent, remainNum - 1));
            }
        }
        return result;
    }

    public static void main(String[] args) {
        // 测试：从[A,B,C,D]中选2个元素的排列
        List<String> array = new ArrayList<>();
        array.add("A");
        array.add("B");
        array.add("C");
        array.add("D");

        List<List<String>> result = permutations(array, 2);
        // 输出结果
        for (List<String> perm : result) {
            System.out.println(perm);
        }
    }
}